import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author: TTDB
 * @create: 2025/10/27
 */
public class BucketSort {
    public static void bucketSort(float[] arr) {
        if (arr.length <= 1) return;

        // 1. 找到数据的最大值和最小值
        float minValue = arr[0];
        float maxValue = arr[0];
        for (float num : arr) {
            if (num < minValue) minValue = num;
            if (num > maxValue) maxValue = num;
        }

        // 2. 根据数据范围确定桶的数量
        int bucketCount = (int) Math.sqrt(arr.length); // 可以根据需要调整桶的数量
        List<Float>[] buckets = new List[bucketCount];
        for (int i = 0; i < bucketCount; i++) {
            buckets[i] = new ArrayList<>();
        }

        // 3. 将数据分配到不同的桶中
        for (float num : arr) {
            int index = (int) ((num - minValue) / (maxValue - minValue + 1) * bucketCount);
            buckets[index].add(num);
        }

        // 4. 对每个桶内部进行排序（使用插入排序）
        for (List<Float> bucket : buckets) {
            Collections.sort(bucket);
        }

        // 5. 将所有桶中的数据合并
        int index = 0;
        for (List<Float> bucket : buckets) {
            for (float num : bucket) {
                arr[index++] = num;
            }
        }
    }

    public static void main(String[] args) {
        float[] arr = {0.42f, 0.32f, 0.23f, 0.52f, 0.72f, 0.12f, 0.72f};
        bucketSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
